class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        result = []
        cur = []
        width = -1
        for w in words:
            if len(w)+1+width<=maxWidth:
                cur.append(w)
                width = width+len(w)+1
            else:
                result.append(cur)
                cur = [w]
                width = len(w)
        result.append(cur)

        if len(result)>0:
            last = ' '.join(result[-1])
            result[-1] = [last]

        lines = []

        for ret in result:
            line = ''
            nChar = sum(map(len, ret))
            nSpace = maxWidth-nChar
            nBlank = len(ret)-1
            space = None
            if nBlank!=0:
                space = [nSpace//nBlank] * nBlank
                nSpaceLeft = nSpace%nBlank
                for i in range(nSpaceLeft):
                    space[i]+=1
            else:
                space = [nSpace]
            i = 0
            while i < len(ret)+len(space):
                if i<len(ret)+len(space):
                    line += ret[i//2]
                    i+=1
                if i<len(ret)+len(space):
                    line += ' '*space[i//2]
                    i+=1
            lines.append(line)
        return lines

print(Solution().fullJustify(["What","must","be","shall","be."], 12))